package daily.year2024.m11;

public class d3 {
    //解法一：暴力递归，超时
    class Solution1 {
        //排列解法
        int[] nums;
        int sum;
        boolean flag;
        public boolean canPartition(int[] nums) {
            int n = nums.length;
            this.nums = nums;
            sum = 0;
            for(int i=0;i < n;i++) {
                sum += nums[i];
            }
            int cnt = n-1, limit = n/2;
            while(cnt >= limit) {
                //从数组中选出n-1个元素
                if(dfsCnt(cnt,0,0)) {
                    return true;
                }
                cnt--;
            }
            return false;
        }
        private boolean dfsCnt(int cnt, int idx, int tmp) {
            if(idx >= nums.length) {
                //返回
                return cnt == 0 && tmp == sum-tmp;
            }
            if(cnt == 0) {
                return tmp == sum-tmp;
            }
            for(int i=idx;i < nums.length;i++) {
                boolean f = dfsCnt(cnt-1,i+1,tmp+nums[i]);
                if(f) {
                    return f;
                }
            }
            return false;
        }
    }

    //解法二：动态规划
    class Solution2 {
        public boolean canPartition(int[] nums) {
            int n = nums.length;
            int sum = 0, maxNum = 0;
            for(int i=0;i < n;i++) {
                sum += nums[i];
                maxNum = Math.max(nums[i],maxNum);
            }
            if(sum % 2 != 0 || maxNum > sum / 2) {
                return false;
            }
            int half = sum / 2;
            boolean[][] dp = new boolean[n][half + 1];
            dp[0][nums[0]] = true;
            for(int i=0;i < n;i++) {
                dp[i][0] = true;
            }
            for(int i=1;i < n;i++) {
                for(int j=1;j <= half;j++) {
                    dp[i][j] = dp[i-1][j];
                    if(j >= nums[i] && !dp[i][j]) {
                        dp[i][j] = dp[i-1][j-nums[i]];
                    }
                }
            }
            return dp[n-1][half];
        }
    }
}
